﻿// 343. 太空电梯 Space Elevator（挑战程序设计竞赛）.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>

using namespace std;



/*

https://www.papamelon.com/problem/343


奶牛们要去太空了！
它们打算用方块建造一座太空电梯。
现在它们有 N 种方块，第 i 种方块有一个特定的高度 h_i，一定的数量 c_i。
为了防止宇宙射线的破坏方块，第 i 种方块的任何部分不能超过高度 a_i。
请用这些方块堆出最高的太空电梯。

输入
第一行，一个整数 N
第二行到 N+1 行，每行三个整数 h_i,a_i,c_i，数字之间用空格分隔。
1≤N≤400，1≤hi≤100，1≤ci≤10，1≤ai≤4×10^4

输出
一个整数，为太空电梯的高度。
样例 1
输入
3
7 40 3
5 23 8
2 52 6

输出
48
*/
//前I个物品能达到的最高高度j  还有物品限制 有高度限制
//
//const int N = 410;
//struct BLOCK {
//	int h, a, c;
//}blocks[N];
//struct BLOCK arr[400 * 10 + 10]; int idx;
//int dp[2][40010];
//int n;
//
//bool cmp(const struct BLOCK& a, const struct BLOCK& b) {
//	return a.a < b.a;
//}

int main()
{
	//cin >> n;
	//for (int i = 1; i <= n; i++) {
	//	cin >> blocks[i].h >> blocks[i].a >> blocks[i].c;
	//}
	//sort(blocks, blocks + n,cmp);
	//idx = 1;
	//for (int i = 1; i <= n; i++) {
	//	for (int j = 0; j < blocks[i].c; j++) {
	//		arr[idx].a = blocks[i].a; arr[idx].h = blocks[i].h;
	//		idx++;
	//	}
	//}
	//dp[0][0] = 1;
	//int curr = 1; int prev = 0;
	//for (int i = 1; i < idx; i++) {
	//	for (int j = 0; j < 40010; j++){
	//		dp[curr][j] = dp[prev][j];
	//		if (j <= arr[i].a && dp[prev][j - arr[i].h]==1) {
	//			dp[curr][j] = max(dp[curr][j], dp[prev][j - arr[i].h]);
	//			if (dp[curr][j] == 1) {
	//				//printf("dp[%d][%d] =%d \n",i,j,dp[i][j]);
	//			}
	//		}
	//	}
	//	swap(curr, prev);
	//}

	//for (int i = 40010; i >=0 ; i--) {
	//	if (dp[prev][i] == 1) {
	//		cout << i << endl; break;
	//	}
	//}

	return 0;
}

 